from LeetCoder import *


class Solution:

    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])

        class Trie(dict):
            id = None

        root = Trie()

        def find(node, arr, id):
            if id == n:
                return node.id

            if 0 in node:
                c = find(node[0], arr, id + 1)
                if c != None:
                    return c
            if arr[id] == 0 and 1 in node:
                c = find(node[1], arr, id + 1)
                if c != None:
                    return c
                
        def add(row,id):
            node = root
            for x in row:
                if x not in node:
                    node[x] = Trie()
                node = node[x]
            node.id = id

        for i, row in enumerate(grid):
            if sum(row) == 0:
                return [i]
            c = find(root, row, 0)
            if c != None:
                return [c, i]
            add(row, i)

        return []


s = Solution()
print(s)
